package 算法.leetcode.offer;

import 算法.leetcode.offer.base.TreeNode;

import java.util.*;

/**
 * @author lchenglong
 * @date 2022/3/19
 */
public class Offer32_II {

    public static void main(String[] args) {
        Offer32_II instance = new Offer32_II();
        // [3,9,20,null,null,15,7]
        List<Integer> list = new ArrayList<Integer>();
        list.add(3);
        list.add(9);
        list.add(20);
        list.add(null);
        list.add(null);
        list.add(15);
        list.add(7);
        TreeNode root = TreeNode.init(list);
        List<List<Integer>> ans = instance.levelOrder(root);
        System.out.println(Arrays.toString(ans.toArray()));
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        while (true){
            int size = queue.size();
            if (size == 0)break;
            List<Integer> list  = new ArrayList<Integer>();;
            for (int i=0;i<size;i++){
                TreeNode node = queue.poll();
                if (node!=null){
                    list.add(node.val);
                    if (node.left!=null)queue.add(node.left);
                    if (node.right!=null)queue.add(node.right);
                }
            }
            if (list.size()>0) {
                ans.add(list);
            }
        }
        return ans;
    }
}
